/*
 * BranchAndBound.c
 *
 *  Created on: 19/mag/2013
 *      Author: Ialenti Andrea, Marangon Fabio
 */
#include "../headers/BranchAndBound.h"
#include "../headers/Printer.h"
#include "../headers/OneTree.h"
#include "../headers/StatusCodes.h"
#include "../headers/Utility.h"
#include "../headers/Heuristic.h"

//	Counter for the number of nodes visited in the recursive decision tree.
int decNodes = 0;

int B_B_Recursive(const Config *cfg, Graph *g, OneTree *t, OneTree *inc, double *zOpt, time_t *t1, time_t *t2, bool verbose) {
	char *funcName = initCharArray(cfg->NAME_LEN);
	sprintf(funcName, "B_B_Recursive");

	uint j, i = 0, free = 0, index[g->size - 1];

	//	Count the number of decision tree nodes visited.
	decNodes++;

	if (verbose && decNodes % cfg->B_B_OUTPUT == 0) {
		fprintf(stdout, "\t\t'%s': %d millions of decision-tree nodes visited, current zOpt = %0.0f\n", funcName, decNodes / 1000000, *zOpt);
		fprintf(stdout, "\t\t\t'%s': elapsed time: %0.2f second(s) (%0.2f normalized time), continuing the branch and bound. . .\n", funcName, difftime(*t2, *t1), difftime(*t2, *t1) * cfg->NORM_TIME);
		fflush(stdout);
	}

	//	Calculate a 1-tree from the current graph.
	Status status = computeOneTree(cfg, g, t);
	if (status != SUCCESS) {
		time(t2);
		freeCharArray(funcName);
		return decNodes;
	}

	//	Check if the new 1-tree improves the current solution.
	if (t->tc < *zOpt) {

		//	If the new 1-tree is actually a tour than update the INCUMBENT tree and the current cost zOpt.
		if (checkTour(t)) {
			cpTree(t, inc);
			*zOpt = inc->tc;

			//	Plot the new incumbent.
			if (verbose) {
				fprintf(stdout, "\t\t'%s': found a better INCUMBENT after visiting %d decision-tree nodes. Current incumbent cost = %0.0f. . .\n", funcName, decNodes, *zOpt);
				char *name = initCharArray(cfg->NAME_LEN);
				char *title = initCharArray(cfg->NAME_LEN);
				sprintf(title, "Current incumbent for '%s', tour cost = %0.0f.", g->name, *zOpt);
				sprintf(name, "%sincumbent_%d.dat", cfg->PLT_PATH, decNodes);
				plotTour(cfg, inc, name, title, cfg->COLOR_BLUE);
				freeCharArray(name);
				freeCharArray(title);
			}

			freeCharArray(funcName);
			time(t2);
			return decNodes;
		}

		//	If the new solution is worst than the current one, prune the decision tree.
	} else if (decNodes != 1) {
		freeCharArray(funcName);
		time(t2);
		return decNodes;
	}
	freeCharArray(funcName);

	//	If any node has more than 2 forced edges prune the decision tree.
	for (j = 0; j < t->size; j++)
		if (t->nodes[j].forced > 2) {
			time(t2);
			return decNodes;
		}

	//	Search for the first node in the 1-tree that has degree greater than 2 (excluding forced edges) and find its edges (nodes indices).
	while (free == 0 && i < t->size)
		//	Find the edges starting from the nodes with degree greater than 2, but consider only those edges that were never forced nor denied in previous steps.
		if (g->nodes[i].degree > 2) {

			for (j = free = 0; j < t->size; j++)
				if (!(g->edges[i][j].cost > -cfg->EPS && g->edges[i][j].cost < cfg->EPS) && g->edges[i][j].cost != -cfg->INF && g->edges[i][j].cost != cfg->INF)
					index[free++] = j;

			//	If no suitable edges were found skip to the next node.
			i = (free == 0) ? i + 1 : i;
		} else
			i++;

	// If there are no free edges, then prune the decision tree.
	if (free == 0) {
		time(t2);
		return decNodes;
	}

	//	Perform the three branches:
	//		1 - first force 2 edges and deny the rest,
	//		2 - then force one edge and deny another,
	//		3 - lastly deny one edge.

	//	Check the number of edges already forced for the current node chosen for branching.
	double *olds = initDblArray(free);
	if (t->nodes[i].forced == 0) {

		//	Force two edges 'e0' and 'e1', deny all the others, then start the first branching.
		if (free > 1) {
			for (j = 0; j < free; j++) {
				olds[j] = g->edges[i][index[j]].cost;
				if (j == 0 || j == 1)
					g->edges[i][index[j]].cost = g->edges[index[j]][i].cost = -cfg->INF;
				else
					g->edges[i][index[j]].cost = g->edges[index[j]][i].cost = cfg->INF;
			}
			B_B_Recursive(cfg, g, t, inc, zOpt, t1, t2, verbose);

			//	Restore the graph.
			for (j = 0; j < free; j++)
				g->edges[i][index[j]].cost = g->edges[index[j]][i].cost = olds[j];
		}

		//	Force the edge 'e0', deny the edge 'e1' and start the second branching.
		if (free > 1) {
			olds[0] = g->edges[i][index[0]].cost;
			olds[1] = g->edges[i][index[1]].cost;
			g->edges[i][index[0]].cost = g->edges[index[0]][i].cost = -cfg->INF;
			g->edges[i][index[1]].cost = g->edges[index[1]][i].cost = cfg->INF;
			B_B_Recursive(cfg, g, t, inc, zOpt, t1, t2, verbose);

			//	Restore the old 'e0', 'e1' values.
			g->edges[i][index[0]].cost = g->edges[index[0]][i].cost = olds[0];
			g->edges[i][index[1]].cost = g->edges[index[1]][i].cost = olds[1];
		}

		//	Deny the edge e0 and start the third branching.
		olds[0] = g->edges[i][index[0]].cost;
		g->edges[i][index[0]].cost = g->edges[index[0]][i].cost = cfg->INF;
		B_B_Recursive(cfg, g, t, inc, zOpt, t1, t2, verbose);

		//	Restore the old e0 value.
		g->edges[i][index[0]].cost = g->edges[index[0]][i].cost = olds[0];

	} else {

		if (t->nodes[i].forced == 1) {

			//	Force the edge 'e0', and deny all the others, then start the first branching.
			for (j = 0; j < free; j++) {
				olds[j] = g->edges[i][index[j]].cost;
				if (j == 0)
					g->edges[i][index[j]].cost = g->edges[index[j]][i].cost = -cfg->INF;
				else
					g->edges[i][index[j]].cost = g->edges[index[j]][i].cost = cfg->INF;
			}
			B_B_Recursive(cfg, g, t, inc, zOpt, t1, t2, verbose);

			//	Restore the graph.
			for (j = 0; j < free; j++)
				g->edges[i][index[j]].cost = g->edges[index[j]][i].cost = olds[j];
		}

		//	Deny the edge 'e0' and start the second branching.
		olds[0] = g->edges[i][index[0]].cost;
		g->edges[i][index[0]].cost = g->edges[index[0]][i].cost = cfg->INF;
		B_B_Recursive(cfg, g, t, inc, zOpt, t1, t2, verbose);

		//	Restore the old 'e0' value.
		g->edges[i][index[0]].cost = g->edges[index[0]][i].cost = olds[0];
	}

	freeDblArray(olds);
	time(t2);
	return decNodes;
}
